//
// Created by Administrator on 2021/8/24.
//
//有 n 个城市通过一些航班连接。给你一个数组flights ，其中flights[i] = [fromi, toi, pricei] ，
// 表示该航班都从城市 fromi 开始，以价格 toi 抵达 pricei。
//
//现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k站中转的路线，
// 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
        /**
         * dp
         * 状态：
         * dp[t][j]:坐了t次航班，到达j的最小花费
         * dp[t][j] = dp[m-1][i] + cost[i][j], (i,j)之间有航线
         * 最多能坐k+1次
         */
        static constexpr int INF = 10000 * 101 + 1;
        vector<vector<int>> dp(k + 2, vector<int>(n, INF));
        dp[0][src] = 0;
        for (int t = 1; t <= k + 1; ++t) {
            for (auto &flight:flights) {
                int i = flight[0], j = flight[1], cost = flight[2];
                dp[t][j] = min(dp[t][j], dp[t - 1][i] + cost);
            }
        }
        int ans = INF;
        for (int i = 1; i <= k + 1; ++i) {
            ans = min(ans, dp[i][dst]);
        }
        return ans == INF ? -1 : ans;
    }
};

class Solution2 {
public:
    struct node {
        int to, price, step;
    };

    int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
        queue<node> q;
        int price = INT_MAX;
        vector<vector<int>> edgs(n, vector(n, 0));
        vector<int> ans(n, INT_MAX);  //一直记录到某个地点的花费最小值
        ans[src] = 0;

        for (auto &flight : flights) {
            edgs[flight[0]][flight[1]] = flight[2];
        }

        q.push((node) {src, 0, -1});

        while (!q.empty()) {
            node temp = q.front();
            q.pop();

            if (temp.to == dst) {
                price = min(price, temp.price);
                continue;
            }

            for (int i = 0; i < n; i++) {
                if (edgs[temp.to][i] == 0) continue;
                //中转数量将等于最大允许中转数且下一站不是目标站直接舍弃。
                if (temp.step == (k - 1) && i != dst) continue;
                if (ans[i] > temp.price + edgs[temp.to][i]) {
                    ans[i] = temp.price + edgs[temp.to][i];
                    q.push((node) {i, ans[i], temp.step + 1});
                }
            }
        }

        return price == INT_MAX ? -1 : price;
    }
};


int main() {
    vector<vector<int>> flights{{0, 1, 100},
                                {1, 2, 100},
                                {0, 2, 500}};
    Solution2 solution;
    cout << solution.findCheapestPrice(3, flights, 0, 2, 1) << endl;
    return 0;
}
